#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, k;
//int q[N];
//
//int quick_sort(int* a, int l, int r, int k)
//{
//	if (l >= r) return a[l];
//
//	int x = a[(l + r) >> 1];
//	int i = l - 1, j = r + 1;
//	while (i < j)
//	{
//		do i++; while (a[i] < x);
//		do j--; while (a[j] > x);
//		if (i < j) swap(a[i], a[j]);
//	}
//
//	int sl = j - l + 1;
//	if (sl >= k) return quick_sort(a, l, j, k);
//	else return quick_sort(a, j + 1, r, k - sl);
//}
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << quick_sort(q, 0, n - 1, k) << endl;
//
//	return 0;
//}
//
//#include <iostream>
//using namespace std;
//
//typedef long long LL;
//const int N = 100010;
//int n;
//int q[N], tmp[N];
//
//LL merge_sort(int* a, int l, int r)
//{
//	if (l >= r) return 0;
//
//	int mid = (l + r) >> 1;
//
//	LL res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
//
//	int k = 0, i = l, j = mid + 1;
//	while (i <= mid && j <= r)
//	{
//		if (a[i] <= q[j]) tmp[k++] = a[i++];
//		else
//		{
//			res += mid - i + 1;
//			tmp[k++] = a[j++];
//		}
//	}
//	while (i <= mid) tmp[k++] = a[i++];
//	while (j <= r) tmp[k++] = a[j++];
//
//	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//
//	return res;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> q[i];
//
//	cout << merge_sort(q, 0, n - 1) << endl;
//
//	return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 100010;
//int n, m;
//int a[N], b[N];
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n; i++) cin >> a[i];
//    for (int i = 0; i < m; i++) cin >> b[i];
//
//    int l1 = 0, l2 = 0;
//
//    while (l1 < n && l2 < m)
//    {
//        while (l2 < m && a[l1] != b[l2])
//            l2++;
//
//        if (l2 == m) break;
//
//        l1++;
//        l2++;
//    }
//
//    if (l1 == n || (l1 == n && l2 == m)) cout << "Yes" << endl;
//    else cout << "No" << endl;
//
//    return 0;
//}

//
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//const int N = 300010;
//int n, m;
//int a[N], s[N];
//
//vector<int> alls;
//vector<pair<int, int>> xc, lr;
//
//int find(int x)
//{
//    int l = 0, r = alls.size() - 1;
//    while (l < r)
//    {
//        int mid = (l + r) >> 1;
//        if (alls[mid] >= x) r = mid;
//        else l = mid + 1;
//    }
//
//    return l + 1;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 0; i < n; i++)
//    {
//        int x, c;
//        cin >> x >> c;
//        alls.push_back(x);
//        xc.push_back({ x, c });
//    }
//
//    for (int i = 0; i < m; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        lr.push_back({ l, r });
//        alls.push_back(l);
//        alls.push_back(r);
//    }
//
//    sort(alls.begin(), alls.end());
//    alls.erase(unique(alls.begin(), alls.end()), alls.end());
//
//    for (auto item : xc)
//    {
//        int i = find(item.first);
//        a[i] += item.second;
//    }
//
//    for (int i = 1; i <= alls.size(); i++) s[i] += s[i - 1] + a[i];
//
//    for (auto item : lr)
//    {
//        int l = find(item.first), r = find(item.second);
//        cout << s[r] - s[l - 1] << endl;
//    }
//
//    return 0;
//}

